perm filename WINGED.DOC[1,BGB] blob
sn#001276 filedate 1972-10-28 generic text, type T, neo UTF8
00100 STANFORD ARTIFICIAL INTELLIGENCE PROJECT OCTOBER 1972
00200 MEMO AIM-XXX
00300
00400 COMPUTER SCIENCE DEPARTMENT REPORT
00500 NO. CS-XXX
00600
00700
00800
00900 WINGED EDGE POLYHEDRON REPRESENTATION.
01000
01100 Bruce G. Baumgart
01200
01300
01400 Abstract: A winged edge polyhedron representation is stated and
01500 a set of primitives that preserve Euler's F-E+V = 2 equation are
01600 explained. Present use of this representation in Artificial
01700 Intelligence for computer graphics and world modeling is illustrated
01800 and its intended future application to computer vision is discribed.
01900
02000
02100 CONTENTS
02200
02300 I. INTRODUCTION.
02400 A. Introduction to World Modeling.
02500 B. Introduction to a Camera Model.
02600 C. Introduction to Body, Face, Edge, Vertex Modeling.
02700
02800 II. DATA STRUCTURE of Winged Edge Polyhedra.
02900 A. Winged Edge Structure.
03000 B. Winged Edge Operations.
03100 C. Elaborations.
03200
03300 III. PRIMITIVES on Polyhedra.
03400 A. Euler Primitives.
03500 B. Solid Primitives.
03600 C. Geometric Primitives.
03700 D. Image Forming Primitives.
03800
03900 IV. APPLICATIONS.
04000 A. Modeling: GEOMED - a 3D drawing editor.
04100 B. Graphics: OCCULT - a hidden line eliminator.
04200 C. Vision: CAREYE - a video region-edge finder.
04300
04400 This research was supported in part by the Advanced Research Projects
04500 Agency of the Office of the Secretary of Defence under contract
04600 SD-183.
00100 FIGURE 1.1 - Example World Model Scenes.
00200 1a. A parking lot scene.
00300 1b. The hand-eye table, arm, camera, and some blocks.
00100 I. INTRODUCTION.
00200
00300 In order to get a computer to deal with the physical world it
00400 must have a data representation on which computations involving
00500 space, time, shape, size, and the appearance of things can be done.
00600 It is my current prejudice that polyhedra provide the proper starting
00700 point for building such a physical world representation. At Stanford
00800 Artificial Intelligence, Binford and Agin have started instead with
00900 spine-cross section models as an alternate approach to the same
01000 problems [reference 1]. Other researchers with somewhat different
01100 goals, are attempting to build semantic, predicate calculus, problem
01200 solving, or startegy planning world models. In any event, this
01300 paper is about a body, face, edge, vertex polyhedron model that is
01400 for modeling objects and scenes of objects for the sake of computer
01500 vision.
01600
01700 Although the data structure to be discussed is not language
01800 dependent, the terminlogy and examples will follow ALGOL and LISP.
01900 Also, the reader is assumed to have some acquaintance with the ideas
02000 associated with the following technical terms:
02100
02200 A: block, node, item, element, atom.
02300 B: link, pointer, address, reference.
02400 C: datum, content, value.
02500 D: list, ring, stack, pdl, tree.
02600 E: dynamic free storage & memory allocation.
02700
02800 A thorough presentation of these terms and ideas can be found in
02900 chapter two of volume one of Knuth's cookbook, `The Art of Computer
03000 Programming' [Reference 7]. The word "ring" used informally in this
03100 paper will always mean a double pointer ring with a head; and as in
03200 LISP, words of memory happen to be able to hold two pointers.
03300
03400 Finally, the reader should be warned that the
03500 advantages of using a winged edge polyhedron representation
03600 rather than some other representation are not explicitly documented
03700 in this paper. To formally demonstrate the advantage of
03750 one representation over another would require running bench mark
03850 problems on implementations of the representations in the same
03950 language and the same environment.
04050 However on an informal testimonial level, I feel the winged edge
04150 representation
00100 FIGURE 1.2 - A Polyhedron Model of a Mechanical Arm.
00100 I. A. Introduction to World Modeling.
00200
00300 I will introduce my requirements for a computer model of the
00400 physical world in terms of its role as a memory. As a memory, a
00500 world model has contents and an addressing mechanism. The kinds of
00600 data that I wish to hold in my world model are:
00700
00800 CONTENT REQUIREMENTS
00900 1. Topological data.
01000 2. Geometric data.
01100 3. Photometric data.
01200 4. Parts tree data.
01300
01400 Topological data has to do with the notion of neighborhood; a
01500 world model has data on what is next to what. A face, edge, vertex
01600 model is essentially dedicated to surface topology; matters of volume
01700 topology are not stored but rather must be computed. Geometric data
01800 has to do with notions such as locus, length, area and volume.
01900 Photometric data includes the locus and nature of light sources, as
02000 well as data on how surfaces reflect, absorb and scatter light. Parts
02100 tree data has to do with the notion that objects are composed of
02200 parts, which I construe as data on the structure of the physical
02300 world rather than as purely an artifact of having structured world
02400 data; that is, I prefer to have the specification of how an entity is
02500 broken into parts be external to my world model. The kinds of data
02600 not included are semantic data (other than body names); physical data
02700 such as mass, inertia tensors, electrical properties and so on; and
02800 cultural data such as whether an object is a toy, tool, or weapon;
02900 with any artistic, religious or market value.
03000
03100 Next the kinds of addressing mechanisms I wish to have, (or
03200 equivalently the input-output modes of the model) are:
03300
03400 ACCESSING REQUIREMENTS
03500 1. Appearance - given a camera, return an image of
03600 what the world would look like from that camera.
03700 2. Recognition - given an image, return the objects
03800 from the world model that appear in that image.
03900 3. Camera Solution - given a recognized image,
04000 find the location & orientation of the camera.
04100 4. Perception - given images, from solved cameras,
04200 place new bodies into the model for portions of
04300 the images that have not yet been recognized.
04400 5. Spatial Accessing - given a locus and radius,
04500 return the portions of objects in that sphere.
04600
04700 Clearly, these are the high level accessing requirements which are
04800 the reasons for having a world model and the design goals for model
04900 building.
00100 FIGURE 1.3 - A Camera Model.
00200
00300 FIGURE 1.4 - Logical & Physical Raster Sizes.
00100 I. B. Introduction to a Camera Model.
00200
00300 As the accessing requirements imply, a world model requires a
00400 special entity called a camera which is used to model image
00500 formation. Although the camera model is important here for a complete
00600 specification of the data, it may be skipped on a first reading. The
00700 particular camera model I have been using lately, is expressed by
00800 eighteen real numbers involving nine degrees of freedom. First there
00900 is the camera lens center locus:
01000
01100 CX, CY, CZ, in world coordinates.
01200
01300 Afixed to the lens center is the camera frame of reference with unit
01400 vectors i, j and k. When the image formed by the camera is placed in
01500 correspondence to a display screen, as illustrated in figure 1.3, the
01600 unit vector i maps into the rightward positive x of the display
01700 screen, and the unit vector j maps into the upward positive y of the
01800 display screen, and the unit vector k comes out of the display screen
01900 to form a right handed coordinate system. Together the three unit
02000 vectors of the camera are the three by three rotation matrix:
02100
02200 IX, IY, IZ
02300 JX, JY, JZ in world coordinates.
02400 KX, KY, KZ
02500
02600 Next, there are three scales which determine the correspondence
02700 between world size and image size. Observe that the world is measured
02800 in physical units of length like meters or feet while computer images
02900 come in integral sizes like 1024 by 1024 or 480 rows by 512 columns,
03000 thus the conversion scales must be in terms of logical image units
03100 per physical world units. In an actual television camera a minute
03200 image (say 9mm by 12mm) is formed on a vidicon tube and that image
03300 has a particular number of rows and columns. It is the little image
03400 on the vidicon that we pretend to model by the six parameters:
03500
03600 LDX, LDY, LDZ Logical raster size.
03700 PDX, PDY, FOCAL Physical raster size.
03800
03900 Where the number named FOCAL, is the focal plane distance which in
04000 this model (with distant objects) can safely be equated with the lens
04100 focal length and can be given in millimeters (conventional lens run
04200 12.5mm to 75mm for 1" TV). The integer LDZ is an artifact so that
04300 the units come out correctly in the Z dimension. Thus the scales
04400 factors are defined:
04500
04600 SCALEX ← -FOCAL*LDX/PDX;
04700 SCALEY ← -FOCAL*LDY/PDY;
04800 SCALEZ ← FOCAL*LDZ;
04900
05000 This simple camera model is used to compute vertex image
05100 coordinates. A more elaborate physical camera model can be found in
05200 Sobel [reference 9].
00100 FIGURE 1.5 Renaissance man looking at a cube.
00100 I. C. Introduction to Body, Face, Edge, Vertex (BFEV) Modeling.
00200
00300 This introduction to BFEV modeling will be informal and
00400 specific to the winged edge model presented in part-II of this paper.
00500 Many of the basic numerical relations which make BFEV models
00600 important are stated in ALGOL notation without proof.
00700
00800 The Vertex.
00900
01000 A vertex is an instance of a point in a Euclidean three
01100 space. The important thing about a vertex is its world locus (with
01200 component names XWC,YWC,ZWC standing for world-coordinates). Vertex
01300 locii are the basic geometric data from which length, area, volume,
01400 face vectors and image positions can be computed. Also a Vertex may
01500 exist simultaneously in one or more image spaces. An image space
01600 (with component names XPP,YPP,ZPP standing for perspective-projected)
01700 is always three dimensional and is determined with respect to a given
01800 camera centered coordinate system (with component names XCC,YCC,ZCC
01900 standing for camera-coordinates). The third image component, ZPP,
02000 is taken inversely proportional to the distance of the vertex from
02100 the camera image plane, ZCC. Using the camera of the previous
02200 section. The transformation of a vertex world locus to a camera
02300 centered locus is:
02400
02500 X ← XWC - CX;
02600 Y ← YWC - CY;
02700 Z ← ZWC - CZ;
02800
02900 XCC ← IX*X + IY*Y + IZ*Z;
03000 YCC ← JX*X + JY*Y + JZ*Z;
03100 ZCC ← KX*X + KY*Y + KZ*Z;
03200
03300 The first three assignment statements are the translation to
03400 the camera frame's origin, the second three assignments are the
03500 rotation to the camera frame's orientation. Next the perspective
03600 projection transformation is computed:
03700
03800 XPP ← SCALEX*XCC/ZCC;
03900 YPP ← SCALEY*YCC/ZCC;
04000 ZPP ← SCALEZ /ZCC;
04100
04200 The XPP and YPP assignments are derived by means of similar
04300 triangles, as is being done by the man in figure 1.5; the Zpp
04400 assignment is for preserving the depth information and the
04500 colinearity of the world in the perspective projected image space. As
04600 given, the PP frame is right handed and vertices in front of the
04700 camera's image plane will have negative Zpp; Zpp values near -FOCAL
04800 are close to the camera and values approaching zero are far away.
04900
05000 A final matter with respect to vertices is their valence. The
05100 valence of a vertex is the number of edges that meet at the vertex. A
05200 vertex valence of three, for example, indicates a trihedral corner.
00100 I. C. Introduction to BFEV Modeling. (continued).
00200
00300 The Edge.
00400
00500 For a start, the structure of an edge need be thought of as
00600 little more than two vertices; the topological subtlety of edges will
00700 be explained later. However, two vertices do define the important
00800 geometric edge data called the 2D line coefficients. Named AA, BB,
00900 CC; these coefficients are computed from the perspective locus of the
01000 edge's endpoints as follows:
01100
01200 AA ← Y1 - Y2;
01300 BB ← X2 - X1;
01400 CC ← X1*Y2 - X2*Y1;
01500
01600 These coefficients appear in the 2D equation of the line that
01700 contains the edge:
01800 0 = AA*X + BB*Y + CC;
01900
02000 When the edge coefficients are normalized:
02100
02200 L ← SQRT(AA↑2+BB↑2);
02300 AA ← AA/L;
02400 BB ← BB/L;
02500 CC ← CC/L;
02600
02700 the line equation gives the distance, of a point X,Y from the line:
02800
02900 Q ← AA*X + BB*Y + CC;
03000
03100 The distance is actually ABS(Q), since Q is negative on one side side
03200 of the line; also if one were standing on the plane at point X1,Y1
03300 facing X2,Y2 the Q positive half-plane would be on your left and the
03400 Q negative half plane would be on your right.
03500
03600 An important operation on two edges is to detect whether or
03700 not they intersect; this can be decided by checking first whether the
03800 endpoints of one edge are in the opposite half planes of the other
03900 edge, and second whether the endpoints of the latter edge are in the
04000 opposite half planes of the first. When both conditions obtain, then
04100 the intersection point can be found:
04200
04300 T ← (A1*B2 - A2*B1);
04400 X ← (B1*C2 - B2*C1)/T;
04500 Y ← (A2*C1 - A1*C2)/T;
04600
04700 An actual compare for intersection should initially check for the
04800 identity case, and for edges with a vertex in common.
00100 I. C. Introduction to BFEV Modeling. (continued).
00200
00300 The Face.
00400
00500 A face is a finite region of plane enclosed by straight
00600 lines. A safe formal face structure could be built by defining a
00700 triangle as three non-colinear vertices and then insisting that all
00800 faces be triangle interiors. Unhappily, BFEV faces are usually
00900 represented as a list of vertices and edges (or by something nearly
01000 equivalent) for the sake of saving memory space. Such `list' faces
01100 are not monolithic but tend to suffer special cases and pathologies
01200 such as:
01300 Coincident or crossing edges,
01400 Holes and Disjointness,
01500 Concavity (& Convexity),
01600 Non-coplanarity.
01700
01800 Like edges, faces have characteristic coefficients. Face coefficients
01900 satisfy the equation of a plane in which the face is embedded:
02000
02100 AA*X + BB*Y + CC*ZZ = KK.
02200
02300 The equation could be divided by KK, but that is undesirable because
02400 the AA, BB, CC are more useful as a unit normal vector, in which case
02500 KK is the distance of the origin from the plane. Given the locii of
02600 three non-colinear vertices, the coefficients of a plane can be
02700 computed by Kramer's rule as follows:
02800
02900 KK ← X1*(Z2*Y3-Y2*Z3)
03000 + Y1*(X2*Z3-Z2*X3)
03100 + Z1*(Y2*X3-X2*Y3);
03200 AA ← (Z1*(Y2-Y3) + Z2*(Y3-Y1) + Z3*(Y1-Y2));
03300 BB ← (X1*(Z2-Z3) + X2*(Z3-Z1) + X3*(Z1-Z2));
03400 CC ← (X1*(Y3-Y2) + X2*(Y1-Y3) + X3*(Y2-Y1));
03500
03600 and normalized:
03700
03800 ABC ← SQRT(AA↑2 + BB↑2 + CC↑2);
03900 AA ← AA/ABC;
04000 BB ← BB/ABC;
04100 CC ← CC/ABC;
04200 KK ← KK/ABC;
04300
04400 If the given vertices V1, V2, V3 had been taken going counter
04500 clockwise about the face as viewed from the exterior of the solid,
04600 then the following relations obtain:
04700
04800 AA*X + BB*Y + CC*Z > KK implies X,Y,Z above the plane.
04900 AA*X + BB*Y + CC*Z = KK implies X,Y,Z in the plane.
05000 AA*X + BB*Y + CC*Z < KK implies X,Y,Z below the plane.
05100
05200 Face coefficients prove useful in both world and image coordinates.
00100 (blank page)
00100 I. C. Introduction to BFEV Modeling. (continued).
00200
00300 POLYHEDRA, BODIES and OBJECTS.
00400
00500 In elementary geometry, a polyhedron is said to be a solid
00600 formed (or bounded) by plane faces; the word "polyhedron" literally
00700 meaning "many-faced". Topologically, simple polyhedra satisfy
00800 Euler's F-E+V=2 equation; where F, E and V are the number of faces,
00900 edges and vertices of the polyhedron respectively. This equation was
01000 known to Descartes in 1640, but the first proof wasn't given until
01100 1752, when Euler proved the relation by considering the graph
01200 corresponding to the edges of polyhedra. A simple polyhedron is one
01300 homeomorphic to a sphere. The rigorous development of volume measure,
01400 and in turn `solid' polyhedra, is not simple; thus it has been easier
01500 to take the topological notion F-E+V=2 as the more primitive
01600 definition of a polyhedron on which to base a data structure and to
01700 proceed towards the appearance of `solidness' which is a more
01800 complicated notion.
01900
02000 Counter to the usual usuage, I define the word "body" to mean
02100 an entity more specific than a polyhedron; the idea being that a
02200 polyhedron is represented by the whole structure of bodies, faces,
02300 edges and vertices. Bodies may have location, orientation and volume
02400 in space. Bodies may be conected to faces, edges and vertices, which
02500 may or may not form a complete polyhedron. It is typical to have
02600 only one body to a polyhedron when representing a rigid object like a
02700 sledge hammer and several bodies to a polyhedron when representing a
02800 flexible object like a man. Furthermore, the body concept is used to
02900 handle the notion of parts and abstract regional objects such as a
03000 parking lot. For example, the Stanford AI Parking Lot is
03100 represented by a body that has three parts: the Near, Mid and Far
03200 Lots. The Near Lot then has aisles and lanes and lamp islands; a lamp
03300 island has a curb and two lamps; a lamp has a base, stem and top.
03400 This parts structure is carried in body nodes. Finally, the word
03500 "object" will be used to refer to physical objects such as a
03600 redwood-tree, building, or roadway.
00100 Figure 1.6
00200 FACE PERIMETER - a face is surrounded by edges and vertices.
00300
00400 VERTEX
00500 ⊗
00600 / \
00700 / \
00800 / \
00900 / \
01000 EDGE / \ EDGE
01100 / \
01200 / FACE \
01300 / \
01400 / \
01500 / \
01600 VERTEX ⊗---------------------⊗ VERTEX
01700 EDGE
01800
01900 Figure 1.7
02000 VERTEX PERIMETER - a vertex is surrounded by edges and faces.
02100
02200 EDGE
02300 |
02400 |
02500 FACE | FACE
02600 |
02700 ⊗ VERTEX
02800 / \
02900 / \
03000 / \
03100 / \
03200 / FACE \
03300 EDGE EDGE
03400
03500 Figure 1.8
03600 EDGE PERIMETER - an edge is surrounded by 2 faces & 2 vertices.
03700
03800 VERTEX
03900
04000 ⊗
04100 |
04200 |
04300 FACE E FACE
04400 |
04500 |
04600 ⊗
04700
04800 VERTEX
00100 I. C. Introduction to BFEV Modeling. (continued).
00200
00300 FOUR KINDS OF BFEV ACCESSING.
00400
00500 1. Accessing by name and serial number.
00600 2. Parts-Tree Accessing.
00700 3. FEV Sequential Accessing.
00800 4. FEV Perimeter Accessing.
00900
01000 A BFEV model has four kinds of accessing. The most
01100 conventional BFEV access is retrieval by symbolic name which requires
01200 a symbol table. Next, between bodies there is Parts-Tree accessing.
01300 At the top of the Parts-Tree is a special body named the world to
01400 which all the other bodies are attached; thus the world body serves
01500 as an OBLIST node. Given a particular body, a list of its sub-parts
01600 can be retrieved as well as its supra-part or "supart". A supart is
01700 the whole entity to which a part belongs, the world being its own
01800 supart.
01900
02000 Within each body there is face, edge and vertex sequential
02100 accessing. Given a body, all its faces, or edges, or vertices need to
02200 be readily available since perspective projection loops thru all the
02300 vertices, and the process of display clipping loops thru all the
02400 edges, and the act of checking for body intersection loops thru all
02500 the faces. In LISP, one might provide FEV sequential accessing by
02600 placing a list of faces, a list of edges and a list of vertices on
02700 the property list of each body, so that a cube might be represented
02800 as:
02900
03000 (DEFPROP CUBE (F1 F2 F3 F4 F5 F6) FACES)
03100 (DEFPROP CUBE (E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12)EDGES)
03200 (DEFPROP CUBE (V1 V2 V3 V4 V5 V6 V7 V8) VERTICES)
03300
03400 Finally, among the faces, edges and vertices of a body there
03500 is perimeter accessing. Faces have a perimeter of edges and vertices
03600 [figure 1.6]; less commonly used, vertices have a perimeter of edges
03700 and faces [figure 1.7]; and of particular note, edges have a
03800 perimeter always formed by two faces and two vertices, [figure 1.8].
03900 Perimeter accessing requires that given a face, edge or vertex, that
04000 the perimeter of that entity be readily accessible. Since the surface
04100 of a polyhedron is orientable, that is has a well defined inside and
04200 outside, (Klein bottles with their crosscaps will not be modeled),
04300 such perimeter lists can be ordered (say clockwise) with respect to
04400 the exterior of the polyhedron. Perimeter accessing is mentioned in
04500 Guzman [reference 6] and Falk [reference 4] and is the underlying
04600 basis of part-II of this paper which presents a polyhedron model
04700 built for accessing and altering face, edge and vertex perimeters.
00100 Figure 2.1 - BASIC NODE STRUCTURE.
00200
00300 BODY-BLOCK FACE-BLOCK EDGE-BLOCK VERTEX-BLOCK
00400 -3. part,copart -3. -3. -3. XWC
00500 -2. -2. -2. -2. YWC
00600 -1. -1. -1. -1. ZWC
00700 0. type 0. type 0. type 0. type
00800 +1. nface,pface +1. nface,pface +1. nface,pface +1.
00900 +2. ned,ped +2. ped +2. ned,ped +2. ped
01000 +3. nvt,pvt +3. +3. nvt,pvt +3. nvt,pvt
01100 +4. +4. +4. ncw,pcw +4.
01200 +5. +5. +5. nccw,pccw +5.
01300 +6. +6. +6. +6.
01400 5 words 2 words 6 words 5 words
01500
01600
01700 Figure 2.2 - THE WINGED EDGE.
01800 (As viewed from the exterior of a solid).
01900
02000 \ /
02100 NCCW(E) \ / PCW(E)
02200 \ /
02300 \ /
02400 \ /
02500 ⊗ PVT(E)
02600 |
02700 |
02800 NFACE(E) E PFACE(E)
02900 |
03000 |
03100 NVT(E) ⊗
03200 / \
03300 / \
03400 / \
03500 NCW(E) / \ PCCW(E)
03600 / \
03700
03800
03900
04000 Figure 2.3 - AN ACTUAL NODE STRUCTURE - SEPTEMBER 1972.
04100
04200 BODY-BLOCK FACE-BLOCK EDGE-BLOCK VERTEX-BLOCK
04300 -3. part,copart -3. AA -3. AA -3. XWC
04400 -2. locor -2. BB -2. BB -2. YWC
04500 -1. pname, -1. CC -1. CC -1. ZWC
04600 0. type,serial 0. type,serial 0. type,serial 0. type,serial
04700 +1. nface,pface +1. nface,pface +1. nface,pface +1. XDC,Tjoint
04800 +2. ned,ped +2. ped +2. ned,ped +2. YDC,ped
04900 +3. nvt,pvt +3. QQ +3. nvt,pvt +3. nvt,pvt
05000 +4. Fcnt,Vcnt +4. KK +4. ncw,pcw +4. XPP
05100 +5. Ecnt,Pcnt +5. +5. nccw,pccw +5. YPP
05200 +6. nbody,pbody +6. alt, +6. alt,pbody +6. Zpp
00100 PART-II. THE WINGED EDGE DATA STRUCTURE.
00200
00300
00400 II. A. Winged Edge Data Structure.
00500
00600 Bodies, Faces, Edges and Vertices are represented by blocks
00700 of contiguously addressed words. A single block size of ten words is
00800 adequate. A single word, like a LISP node, can hold two addresses or
00900 a floating point number. The BFEV blocks are pointed at by the
01000 address of their word numbered zero which contains control bits
01100 indicating whether the block is a body, face, edge or vertex. Figure
01200 2.1 illustrates the block format that is being presented as an
01300 example of a winged edge data structure; a minimal number of words
01400 for each block is indicated.
01500
01600 The basic geometric datum is the vertex locus, which is
01700 stored in three words of each vertex block at positions -3, -2, -1;
01800 these positions are named XWC, YWC, ZWC respectively; the letters
01900 "WC" standing for "world coordinates".
02000
02100 The basic topological data are the three rings of the body;
02200 (a ring of faces, a ring of edges, and a ring of vertices) and the
02300 winged edge pointers (eight such pointers in each edge block,and one
02400 such pointer in each face and vertex block). The face, edge and
02500 vertex ring pointers are stored at positions +1, +2, +3; each
02600 position has two names: NFACE, NED, NVT for the left pointers
02700 respectively; and PFACE, PED, PVT for the right. A face, edge or
02800 vertex can only belong to one body and so there is only one body node
02900 in a given face, edge or vertex ring; and that body node serves as
03000 the head of the ring. The reason for double pointer rings is for the
03100 sake of rapid deletion; other minor advantages would not justify the
03200 use of double rings.
03300
03400 The eight WINGED pointers of an edge block include: two
03500 pointers to the faces of that edge, two pointers to the vertices of
03600 that edge, and four pointers to the next edges clockwise and counter
03700 clockwise in each of that edge's two faces; these last four pointers
03800 are called the wings of that edge. As figure 2.2 suggests, four of
03900 these eight pointers are stored in the same positions and referred to
04000 by the same names as the face and vertex ring pointers; namely the
04100 NFACE, PFACE, NVT and PVT pointers. There are four ways in which a
04200 pair of faces and a pair of vertices can be placed into the two face
04300 positions and two vertex positions of an edge; by constraining these
04400 choices two bits are implicitly encoded, one bit is called the edge
04500 parity, and the other is called the surface parity; these bits are
04600 explained later. Finally, the single winged edge pointer found in
04700 faces and vertices is kept in the position named PED and it points to
04800 one of the edges belonging to that face or vertex.
04900
05000 Although the vertices in figure 2.2 are shown with three
05100 edges, vertices may have any number of edges; those other potential
05200 edges would not be directly connected to E and so were not shown.
00100 A SUMMARY OF WINGED EDGE OPERATIONS.
00200
00300
00400 DYNAMIC STORAGE ALLOCATION.
00500
00600 1. Q ← GETBLK(SIZE);
00700 2 RELBLK(Q,SIZE);
00800
00900
01000 BFEV MAKE & KILL OPERATIONS.
01100
01200 1. BNEW ← MKB(B); KLB(BNEW);
01300 2. FNEW ← MKF(B); KLF(B,FNEW);
01400 3. ENEW ← MKE(B); KLE(B,ENEW);
01500 4. VNEW ← MKV(B); KLV(B,VNEW);
01600
01700
01800 FETCH LINK AND STORE LINK OPERATIONS.
01900
02000 1. F ← NFACE(Q); F ← PFACE(Q); NFACE.(F,Q); PFACE.(F,Q);
02100 2. E ← NED(Q); E ← NED(Q); NED.(E,Q); PED.(E,Q);
02200 3. V ← NVT(Q); V ← NVT(Q); NVT.(V,Q); PVT.(V,Q);
02300 4. A ← NCW(E); A ← PCW(E); NCW.(A,E); PCW.(A,E);
02400 5. A ← NCCW(E); A ← PCCW(E); NCCW.(A,E); PCCW.(A,E);
02500
02600
02700 WING LINK OPERATIONS.
02800
02900 1. WING(E1,E2);
03000 2. INVERT(E);
03100
03200
03300 PERIMETER FETCH OPERATIONS.
03400
03500 1. E ← ECW(E,Q);
03600 2. E ← ECCW(E,Q);
03700 3. F ← FCW(E,V);
03800 4. F ← FCCW(E,V);
03900 5. V ← VCW(E,F);
04000 6. V ← VCCW(E,F);
04100 7. Q ← OTHER(E,Q);
04200
04300
04400 PARTS TREE OPERATIONS.
04500
04600 1. B ← PART(B); B ← COPART(B);
04700 2. B ← BODY(Q); B ← SUPART(B);
04800 3. ATT(B1,B2); ATTACH(B1,B2);
04900 4. DET(B); DETACH(B);
00100 II. B. The Winged Edge Operations.
00200
00300 Dynamic Storage Allocation.
00400
00500 At the very bottom, of what is becoming a rather deep nest of
00600 primitives within primitives, are the two dynamic storage allocation
00700 functions GETBLK and RELBLK. GETBLK allocates from 1 to 4K words of
00800 memory space in a contiguous block and returns the machine address of
00900 the first word of that block. RELBLK releases the indicated block to
01000 the available free memory space. (It is sad that the machines of our
01100 day do not come with dynamic free storage). A good reference for
01200 implementing such dynamic storage, mentioned earlier, is Knuth
01300 [reference 7]. Although a fixed block size of ten or fewer words can
01400 be made to handle the BFEV entities, grandiose and fickle research
01500 applications (as well as memory use optimization) demand the
01600 flexibility of a variable block size.
01700
01800 BFEV Make & Kill Operations.
01900
02000 Just above the free storage routines are the four pairs of
02100 make and kill operations. The MKB operation creates a body block and
02200 attaches it as a sub-part of the given body. The world body always
02300 exists so that MKB(WORLD) will make a body attached to the world. In
02400 this paper, the terms `attach' and `detach' refer to operations on
02500 the parts-tree linkages. The FEV make operations: MKF, MKE, MKV
02600 create the corresponding FEV entities and place them in their
02700 respective FEV rings of the given body. In the current
02800 implementation, the FEV makers set the type bits of the entity, and
02900 increment the proper total FEV counter, as well as the proper body
03000 FEV counter in the given body's node, (the Fcnt, Ecnt, Vcnt node
03100 positions are shown in figure 2.3). The kill operations: KLB, KLF,
03200 KLE, and KLV; delete the entity from its ring (or remove it from the
03300 parts-tree), release its space by calling RELBLK, and then decrement
03400 the appropriate counters. The body of the entity is needed by the
03500 kill primitives and can be provide directly as an argument or if
03600 missing, will be found in the data by the primitive itself.
03700
03800 Fetch Link and Store Link Operations.
03900
04000 Each of the fetch link and store link operations named in the
04100 summary is a single machine instruction that accesses the
04200 corresponding link position in a node. Once BFEV nodes exist, with
04300 their rings and parts-tree already in place; the fetch and store link
04400 operations are used to construct or modify a polyhedron's surface. At
04500 this lowest level, constructing a polyhedron requires three steps:
04600 first the two vertex and two face pointers are placed into each edge
04700 in counter clockwise order as they appear when that edge is viewed
04800 from the exterior of the solid; second an edge pointer is placed in
04900 each face and vertex, so that one can later get from a given face or
05000 vertex to one of its edges; and third the edge wings are linked so
05100 that all the ordered perimeter accessing operations described below
05200 will work. Wing linking is facilitated by the WING operation.
00100 FIGURE 2.4 - MIDPOINT EXAMPLE (see text on page 20).
00200
00300 \ pvt /
00400 \ /
00500 nccw \ / pcw
00600 \ /
00700 V ⊗
00800 |
00900 ENEW |
01000 | nvt
01100 VNEW ⊗
01200 | pvt
01300 E |
01400 |
01500 ⊗
01600 / \
01700 ncw / \ pccw
01800 / \
01900 / nvt \
02000
02100 INTEGER PROCEDURE MIDPOINT (INTEGER E);
02200 BEGIN "MIDPOINT"
02300 INTEGER B,ENEW,VNEW,V1,V2;
02400
02500 α CREATE A NEW EDGE AND VERTEX;
02600 B ← BODY(E);
02700 VNEW ← MKV(B);
02800 ENEW ← MKE(B);
02900
03000 α GET VERTICES AND FACES CONNECTED TO EDGES;
03100 PVT.(PVT(E),ENEW);
03200 PVT.(VNEW,E);
03300 NVT.(VNEW,ENEW);
03400 PFACE.(PFACE(E),ENEW);
03500 NFACE.(NFACE(E),ENEW);
03600
03700 α GET EDGES CONNECTED TO VERTICES;
03800 IF PED(V)=E THEN PED.(ENEW,V);
03900 PED.(ENEW,VNEW);
04000
04100 α LINK THE WINGS TOGETHER;
04200 WING(NCCW(E),ENEW);WING(PCW(E),ENEW);
04300 NCW.(E,ENEW);PCCW.(E,ENEW);
04400 PCW.(ENEW,E);NCCW.(ENEW,E);
04500
04600 α PLACE VNEW AT MIDPOINT POSITION;
04700 V1 ← PVT(ENEW); V2 ← NVT(E);
04800 XWC(VNEW) ← (XWC(V1)+XWC(V2)) * 0.5;
04900 YWC(VNEW) ← (YWC(V1)+YWC(V2)) * 0.5;
05000 ZWC(VNEW) ← (ZWC(V1)+ZWC(V2)) * 0.5;
05100 RETURN(VNEW);
05200 END "MIDPOINT";
00100 The Wing Link Operation.
00200
00300 The WING operation stores edge pointers into edges so that
00400 the face perimeters and vertex perimeters are made; and so that
00500 surface parity is preserved. Given two edges which have a vertex and
00600 a face in common, the WING operation places the first edge in the
00700 proper relationship (PCW, NCCW, NCW, or PCCW) with respect to the
00800 second, and the second in the proper relationship with respect to the
00900 first. The INVERT operation swaps the vertex, face, clockwise wing,
01000 and counter clockwise wing pointers of an edge. INVERT preserves
01100 surface parity, but flips edge parity.
01200
01300 The Midpoint Example.
01400
01500 In figure 2.4 an example of how the operations given so far
01600 could be used to code a midpoint primitive is shown. The example
01700 midpoint primitive takes an edge argument and splits it in two by
01800 making a new edge and a new vertex and by placing them into the
01900 polyhedron with the topology shown in the diagram. Then the midpoint
02000 locus is computed and the new vertex is return. The ALGOL notation
02100 used is SAIL, which allows defining the character "α" as a COMMENT
02200 delimiter and allows defining XWC as a real number from the special
02300 array named MEMORY. The MEMORY array in SAIL is the job's actual
02400 machine memory space and gives the user the freedom of accessing any
02500 word in his core image.
02600
02700 The Parts-Tree Operations.
02800
02900 As shown in figure 2.1, each body node has two parts-tree
03000 links named PART and COPART. The PART link is the head of a list of
03100 sub-parts of the body. When a body has no sub-parts the PART link is
03200 the negative of that body's pointer; that is the body points at
03300 itself. When a body has parts, the first part is pointed at by PART
03400 and the second is pointed at by the COPART link of the first and so
03500 on until a negative pointer is retrieved which indicates the end of
03600 the parts list. The negative pointer at the end of a parts list
03700 points back to the orginal body, which is the supra-part or "supart"
03800 of all those bodies in that list.
03900
04000 The parts may be accessed by its link names PART and COPART.
04100 Also the SUPART of a body returns the (positive) pointer to the
04200 supart of a body. The BODY operation returns the body to which a face
04300 edge or vertex belongs; this might be found by CDR'ing a FEV ring
04400 until a body node is reached, but for the sake of speed each edge (as
04500 shown in figure 2.3) has a PBODY link which points back to the body
04600 to which the edge belongs, and since each face and vertex points at
04700 an edge, the body of an FEV entity can be retrieved by fetching only
04800 one or two links.
00100 Part Tree Operations (continued).
00200
00300 The parts-tree is altered by the DET(B) operation which
00400 removes a body B from its supart and leaves it hanging free; and the
00500 ATT(B1,B2) operation which places a free body B1 into the parts list
00600 of a body B2. Since bodies are made attached to the world body and
00700 generally kept attached to something, two further parts-tree
00800 operations are provided, compounding the first two in the necessary
00900 manner. The DETACH(B) operation DET's B from its current owner and
01000 ATT's it to the world; and the ATTACH(B1,B2) operation will DET B1
01100 from its supart and attach it to a new supart. In normal (one world)
01200 circumstances one only needs to use ATTACH to build things.
01300
01400 Perimeter Fetch and Store Operations.
01500
01600 There are seven perimeter fetch primitives, which when given
01700 an edge and one of its links will fetch another link in a certain
01800 fashion. Using the winged edge data structure these primitives are
01900 easily implemented in a few machine instructions which test the type
02000 bits and typically do one or two compares. Clockwise and counter
02100 clockwise are always determined from the outside of a polyhedron
02200 looking down on a particular face, edge or vertex. I apologize for
02300 the high redundancy on the next page, but felt that it was necessary
02400 to make the explanations independent for reference.
02500
02600
02700 FIGURE 2.5 - Face Perimeter Accessing with respect to edge E.
02800
02900 VCCW(E,F) ⊗-------E-------⊗ VCW(E,F)
03000 \ /
03100 \ F /
03200 ECCW(E,F) ECW(E,F)
03300 \ /
03400 \ /
03500 \ /
03600 \ /
03700 ⊗
03800
03900
04000 FIGURE 2.6 - Vertex Perimeter Accessing with respect to edge E.
04100
04200 E
04300 |
04400 |
04500 FCCW(E,V) | FCW(E,V)
04600 ⊗ V
04700 / \
04800 / \
04900 / \
05000 / \
05100 ECCW(E,V) ECW(E,V)
00100 The Perimeter Fetch Operations.
00200
00300
00400 E ← ECW(E,F); Get Edge Clockwise from E about F's perimeter.
00500 E ← ECCW(E,F); Get Edge Counter Clockwise from E about F's perimeter.
00600
00700 Given an edge and a face belonging to that edge, the ECW
00800 fetch primitive returns the next edge clockwise belonging to the
00900 given face's perimeter and the ECCW fetch primitive returns the next
01000 edge counter clockwise belonging to the given face's perimeter.
01100
01200 E ← ECW(E,V); Get Edge Clockwise from E about V's perimeter.
01300 E ← ECCW(E,V); Get Edge Counter Clockwise from E about V's perimeter.
01400
01500 Given an edge and a vertex belonging to that edge, the ECW
01600 fetch primitive returns the next edge clockwise belonging to the
01700 given vertex's perimeter and the ECCW fetch primitive returns the
01800 next edge counter clockwise belonging to the given vertex's
01900 perimeter.
02000
02100 F ← FCW(E,V); Get the face clockwise from E about V.
02200 F ← FCCW(E,V); Get the face counter clockwise from E about V.
02300
02400 Given an edge and a vertex belonging to that edge, the FCW
02500 fetch primitive returns the face clockwise from the given edge about
02600 the given vertex and the FCCW fetch primitive returns the face
02700 counter clockwise from the given edge about the given vertex.
02800
02900 V ← VCW(E,F); Get the vertex clockwise from E about F.
03000 V ← VCCW(E,F); Get the vertex counter clockwise from E about F.
03100
03200 Given an edge and a face belonging to that edge, the VCW
03300 fetch primitive returns the vertex clockwise from the given edge
03400 about the given face and the VCCW fetch primitive returns the vertex
03500 counter clockwise from the given edge about the given face.
03600
03700 F ← OTHER(E,F); Get the other face of an edge.
03800 V ← OTHER(E,V); Get the other vertex of an edge.
03900
04000 Given an edge and one face of that edge the OTHER fetch
04100 primitive returns the other face belonging to that edge. Given an
04200 edge and one vertex of that edge the OTHER fetch primitive returns
04300 the other vertex belonging to that edge.
00100 (blank page)
00100 II. C. Elaborations on Winged Edge Structure.
00200
00300 In this section, some variations on the basic winged
00400 edge structure are given. These variations arise as adaptations for
00500 my application, and as unimplemented ideas for improvements. The
00600 adaptations, shown in figure 2.3, include adding serial numbers and
00700 ALT links to all the faces, edges and vertices. The serial numbers
00800 provide another way of addressing and are especially useful during
00900 input and output. The ALT link is used for pointing to additional but
01000 temporary data; the most elaborate ALT data has to do with edges
01100 during a hidden line elimination. Sacrificing memory space for speed
01200 and flexibility, the face and edge coefficients are stored in each
01300 node, and the image coordinate (Xpp,Ypp,Zpp) and display coordinates
01400 (Xdc,Ydc) are added to each vertex. In elaborate systems, the image
01500 coordinates model a camera and the display coordinates refer to
01600 location on a display console. Having two tiers of image
01700 coordinates allows scrolling about the modeled image without changing
01800 the camera (or heaven forbidden, having to redo a hidden line
01900 elimination). The remaining so far unmentioned names include: the
02000 Tjoint link in vertices which is for shadow and hidden line
02100 operations, the the QQ word in faces which contains photometric data,
02200 and the LOCOR and PNAME links of a body node, which point to a
02300 location-orientation matrix and an ASCII print name respectively.
02400
02500 Sacrificing speed for the sake of memory, the effect of
02600 having most of the extra data mentioned above can be achieved by
02700 recomputing it rather than fetching it. Furthermore, the winged data
02800 structure can be made slightly smaller by eliminating the face and
02900 vertex rings. Face and vertex sequential accessing can still be done
03000 by having two marking bits in each face and vertex,and by then going
03100 thru the edge ring looking at the two faces and two vertices of each
03200 edge for ones that are not freshly marked. It would be nice if such
03300 economizing could be done below the level of the operations.
03400
03500 Besides optimizations, the next improvement idea I would like
03600 to attempt would be to split the notion of a body into the two
03700 notions of a "part" and a "cell". Parts would have the parts tree
03800 and names that bodies now have, whereas a cell would have volume and
03900 face structure. In this hypothetical Cell, Face, Edge, Vertex (CFEV)
04000 model, each face could point to a cell on either side of it, the cell
04100 with the lower serial number (or something) being construed as
04200 exterior. Cell number zero would be the infinite void of three space
04300 in which everything is embedded. The trouble with CFEV is that the
04400 important matter of a polyhedron surface has to be salvaged; it can
04500 not be abandoned, because models without good surface representations
04600 can not predict appearance, which is one of my requirements.
00100 SUMMARY OF POLYHEDRON PRIMITIVES.
00200
00300 A. EULER PRIMITIVES.
00400
00500 1. BNEW ← MKBFV; make a body, face & vertex.
00600 2. KLBFEV(Q); kill a body & all its pieces.
00700 3. VNEW ← MKEV(F,V); make edge & vertex.
00800 4. ENEW ← MKFE(V1,F,V2); make face & edge.
00900 5. VNEW ← ESPLIT(E); split an edge.
01000 6. F ← KLFE(ENEW); kill face & edge leaving a face.
01100 7. E ← KLEV(VNEW); kill edge & vertex leaving an edge.
01200 8. V ← KLVE(ENEW); kill vertex & edge leaving a vertex.
01300 9. B ← GLUE(F1,F2); glue two faces together.
01400 * 10. BNEW ← UNGLUE(E); unglue along a seam containing E.
01500
01600 B. SOLID PRIMITIVES.
01700
01800 1. VPEAK ← PYRAMID(F); form a pyramid on a face.
01900 2. F ← PRISM(F); form a rectangular prism.
02000 3. F ← CWPRISMOID(F) form a clockwise prismoid.
02100 4. F ← CCWPRISMOID(F); form a counter clockwise prismoid.
02200 5. ROTCOM(F); complete a solid of rotation.
02300 6. FVDUAL(B); form face vertex dual of a body.
02400 7. BNEW ← MKCOPY(B); make a copy of a body.
02500 8. EVERT(B); turn a body surface inside out.
02600 9. B1 ← BUN(B1,B2); form union of body interiors.
02700 10. B1 ← BIN(B1,B2); form intersection of body interiors.
02800
02900 C. GEOMETRIC PRIMITIVES.
03000
03100 1. TRANSLATE(Q,R);
03200 2. ROTATE(Q,R);
03300 3. DILATE(Q,R);
03400 4. REFLECT(Q,R);
03500
03600 D. IMAGE PRIMITIVES.
03700
03800 1. PROJECTOR(CAMERA,WORLD);
03900 2. ELIST←CLIPER(WINDOW,WORLD);
04000 3. OCCULT(WORLD);
04100 * 4. SHADOW(SUN,WORLD);
04200 * 5. TV ← MKVID(WINDOW,WORLD);
04300 * 6. B2D ← MKB2D(WINDOW,WORLD);
04400 * 7. B2D ← CAREYE(TV);
04500
04600 * under construction, Oct 1972.
00100 III. PRIMITIVES ON POLYHEDRA.
00200
00300 In this section a number of primitives for doing things to
00400 polyhedra are explained. Although these primitives are currently
00500 implemented using the winged edge data structure, they do not require
00600 a particular polyhedron representation. Indeed, many of these
00700 primitives were originally implemented in a LEAP polyhedron
00800 representation very similar to that of Falk, Feldman and Paul
00900 [reference 5]. Thus, the primitives of this section are on a level
01000 logically independent from the operations of the previous section.
01100
01200 Another aspect of these primitives is that they can be used
01300 as the basis of a "graphics language" or more accurately as a package
01400 of subroutines for geometric modeling. In this vein, the primitives
01500 are currently collected as a package called GEOMES for Geometric
01600 Modeling Embedded in SAIL; and as GEOMEL, Geometric Modeling Embedded
01700 in LISP. A third language, called GEOMED, arises out of the command
01800 language of a geometric model editor based on the primitives.
01900
02000 The primitives are shown in four groups in the summary. The
02100 first group, the Euler Primitives, were inspired by Coxeter's proof
02200 of Euler's formula, section 10.3 of [reference 2]. Although the proof
02300 only required three primitives, additional ones of the same ilk were
02400 developed for convenience. The second group is composed of some
02500 polyhedron primitives that were coded using the Euler primitives. The
02600 third group is for primitives that move bodies, faces, edges and
02700 vertices; or compute geometric values such as length and volume. This
02800 group is underdeveloped for two reasons: one, because I have done
02900 these computations ad hoc to date; and two, because they imply the
03000 subject of animation which is large and difficult and not of central
03100 importance to vision. With the exception of the camera, my worlds are
03200 nearly (but not absolutely) static. A less impoverished geometric
03300 group will be presented in the future. The final group, has three
03400 well developed primitives for making 2D images; and several
03500 primitives that when finished will realize part of the vision system
03600 that I am trying to build.
00100 III. A. Euler Primitives.
00200
00300 As mention above, the Euler primitives are based on the Euler
00400 Equation F-E+V = 2*B-2*H; where F, E, V, B and H stand for the number
00500 of faces, edges, vertices, bodies and handles that exist. The term
00600 "handle" comes from topology, and is the number of well formed holes
00700 in a surface; a sphere has no handles, a torus has one handle, and an
00800 IBM flowcharting template has 26 handles. The Euler equation
00900 restricts the possible topologies of FEV graphs that can be
01000 polyhedra; although such Eulerian polyhedra do not necessarily
01100 correspond to what we normally call a solid classical polyhedron.
01200 Strict adherence to constructing a polyhedron that satisfies Euler
01300 equation F-E+V = 2*B - 2*H would require only four primitives:
01400
01500 +F -E +V = 2*B - 2*H
01600
01700 1. Make Body, Face and Vertex +1....+1....+1......
01800 2. Make Edge and Vertex. ...-1 +1............
01900 3. Make Face and Edge. +1 -1...............
02000 4. Glue two faces of one body. -2 +N -N..........+1
02100 4.' Glue two faces of two bodies. -2 +N -N....-1......
02200
02300 However, the four corresponding destructive primitives are also
02400 possible and desirable:
02500 +F -E +V = 2*B - 2*H
02600
02700 1. Kill Body, Face and Vertex -1....-1....-1......
02800 2. Kill Edge and Vertex. ...+1 -1............
02900 3. Kill Face and Edge. -1 +1...............
03000 4. Unglue along a seam. +2 -N +N..........-1
03100 4.' Unglue along a seam. -2 +N -N....+1......
03200
03300 And finally the operation of splitting an edge at a midpoint into two
03400 edges became so important in forming T-joints during hidden line
03500 elimination that the ESPLIT primitive was introduced in place of the
03600 equivalent KLFE, MKEV, MKFE sequence.
03700
03800 In using the Euler primitives, some non-classical polyhedra
03900 are tolerated as transitional states of the construction; these
04000 transitional states are called:
04100
04200 Seminal Polyhedron.
04300 Wire Polyhedron.
04400 Lamina Polyhedron.
04500 Shell Polyhedron.
04600 Face with Wire Spurs on its perimeter.
04700
04800 A seminal polyhedron is like a point; a wire polyhedron is linear
04900 with two ends like a single piece of wire; lamina and shell polyhedra
05000 are surfaces, and the picturesque phrase about spurs is a restriction
05100 on how faces are dissected into more faces. These terms will be
05200 explained in more detail when they are needed.
00100 III. A. Euler Primitives.
00200
00300
00400 1. BNEW ← MKBFV; Make Seminal Body.
00500
00600 The MKBFV primitive returns a body with one face and one
00700 vertex and no edges. Other bodies are formed by applying primitives
00800 to the seminal MKBFV body. The seminal body is initially attached as
00900 a part of the world.
01000
01100
01200 2. KLBFEV(BNEW); Kill Body and all its pieces.
01300
01400 The KLBFEV primitive will detach and delete from memory the
01500 body given as an argument as well as all its faces, edges, vertices
01600 and sub-parts.
01700
01800
01900 3. VNEW ← MKEV(F,V); Make an edge and a vertex.
02000
02100 The MKEV primitive takes a face, F, and a vertex, V, of F's
02200 perimeter and it creates a new edge, ENEW, and a new vertex, VNEW.
02300 ENEW and VNEW are called a "wire spur" at V on F. MKEV returns the
02400 newly made vertex, VNEW; ENEW can be reached since PED(VNEW) is
02500 always ENEW. Only one wire spur is allowed at V on F at a time.
02600
02700 When applied to the face of a seminal body, MKEV forms the
02800 special polyhedron called a "wire" and returns the new vertex as the
02900 "negative" end of the wire. A wire polyhedron is illustrated in
03000 figure 3.1. When applied to the negative end of a wire, MKEV extends
03100 the wire; however if applied to any other vertex of the wire, MKEV
03200 refuses to change anything and merely returns its vertex argument.
03300
03400 Figure 3.1 - A Wire Polyhedron. Figure 3.2 - VNEW←MKEV(F,V);
03500
03600 seminal vertex ⊗ V1 +V
03700 positive end +| of wire. /|\
03800 | E1 / |←←←←ENEW spur.
03900 -| / | \
04000 ⊗ V2 / -VNEW \
04100 +| / \
04200 | E2 / F \
04300 negative end -| of wirer / \
04400 latest vertex ⊗ V3 ⊗---------------⊗
00100 FIGURE 3.4 - TWO EXAMPLES USING EULER PRIMITIVES. (see page 30).
00200
00300 α MAKE A CUBE;
00400 INTEGER PROCEDURE MKCUBE;
00500 BEGIN "MKCUBE"
00600 INTEGER B,F,E,V1,V2,V3,V4;
00700 α CREATE SEMINAL POLYHEDRON;
00800 B ← MKBFV; F ← PFACE(B); V1 ← PVT(B);
00900 XWC(V1)←+1; YWC(V1)←+1; ZWC(V1)←-1;
01000 α MAKE SEMINAL POLYHEDRON INTO A LAMINA POLYHEDRON;
01100 V2 ← MKEV(F,V1); XWC(V2)←-1;
01200 V3 ← MKEV(F,V2); YWC(V3)←-1;
01300 V4 ← MKEV(F,V3); XWC(V4)←+1;
01400 F ← MKFE(V1,F,V4);
01500 α MAKE FOUR SPURS ON THE LAMINA;
01600 V1 ← MKEV(F,V1); ZWC(V1)←+1;
01700 V2 ← MKEV(F,V2);
01800 V3 ← MKEV(F,V3);
01900 V4 ← MKEV(F,V4);
02000 α JOIN SPURS TO FORM FINAL FACES;
02100 E ← MKFE(V1,F,V2);
02200 E ← MKFE(V2,F,V3);
02300 E ← MKFE(V3,F,V4);
02400 E ← MKFE(V4,F,V1);
02500 RETURN(B);
02600 END "MKCUBE";
02700
02800
02900 α FORM A PYRAMID ON A FACE;
03000 INTEGER PROCEDURE PYRAMID (INTEGER F);
03100 BEGIN "PYRAMID"
03200 INTEGER V,V0,E,E0,PEAK,EX;
03300 REAL X,Y,Z; INTEGER I;
03400 X←Y←Z←I←0;
03500 α GET A VERTEX OF THE FACE AND MAKE A SPUR TO A PEAK;
03600 E←E0←PED(F);
03700 V0 ← VCW(E0,F);
03800 PEAK ← MKEV(F,V0);
03900 α CONNECT THE OTHER VERTICES OF THE FACE TO THE PEAK;
04000 WHILE TRUE DO
04100 BEGIN
04200 V ← VCCW(E,F);
04300 X←X+XWC(V); Y←Y+YWC(V); Z←Z+ZWC(V);
04400 INCREM(I);
04500 IF V=V0 THEN DONE;
04600 E ← ECCW(E,F);
04700 EX ← MKFE(PEAK,F,V);
04800 END;
04900 α POSITION THE PEAK VERTEX AT THE CENTER OF THE FACE;
05000 XWC(PEAK)←X/I; YWC(PEAK)←Y/I; ZWC(PEAK)←Z/I;
05100 RETURN(PEAK);
05200 END "PYRAMID";
00100 4. ENEW ← MKFE(V1,F,V2);
00200
00300 The MKFE primitive can be thought of as a face split. Given
00400 a face and two of its vertices, MKFE forms a new face on the
00500 clockwise side of the line V1 to V2 leaving the old face on the
00600 counter clockwise side. V1 becomes the PVT of ENEW, V2 becomes the
00700 NVT of ENEW, F becomes the PFACE of ENEW and FNEW becomes the NFACE
00800 of ENEW; also ENEW becomes the PED of F and FNEW.
00900
01000
01100 Figure 3.3 - MKFE and KLFE.
01200
01300 BEFORE MKFE AFTER ENEW←MKFE(V1,F,V2)
01400 ⊗ ⊗ ⊗ ⊗
01500 / \ / \ / \ / \
01600 / \ / \ / \ / \
01700 / \ / \ / \ / \
01800 / ⊗ \ / +V1 \
01900 / \ / -FNEW | +F \
02000 ⊗ F ⊗ ⊗ |←←←ENEW ⊗
02100 \ / \ | /
02200 \ ⊗ / \ -V2 /
02300 \ / \ / \ / \ /
02400 \ / \ / \ / \ /
02500 \ / \ / \ / \ /
02600 ⊗ ⊗ ⊗ ⊗
02700 AFTER F←KLFE(ENEW); BEFORE KLFE
02800
02900 MKFE is also used to join the two ends of a wire polyhedron
03000 to form a "lamina"; or the two ends of wire spurs to split a face; or
03100 an end of a wire spur and a regular perimeter vertex to split a face.
03200 A "lamina polyhedron" has only two faces and thus no volume.
03300
03400
03500 EULER EXAMPLES.
03600
03700 The use of the primitives discussed so far is illustrated by
03800 the example subroutines in figure 3.4 on page 29. The make cube
03900 subroutine starts by placing a seminal vertex at (1,1,1); Then a wire
04000 of three edges is made using the MKEV primitive. As the code implies,
04100 MKEV places its new vertex at the locus of the old one. The ends of
04200 the wire are joined with a MKFE to form a lamina polyhedron, then a
04300 spur is placed on each of the vertices of the lamina, and finally the
04400 spurs are joined.
04500
04600 The pyramid example is more realistic, since polyhedra are
04700 not generated ex nihil, but rather arise out of the vision routines
04800 and the geometric editor. PYRAMID takes a face as an argument (which
04900 is assumed to have no spurs) and runs a spur from one vertex to the
05000 middle of the faces, then all the remaining vertices of the face are
05100 joined to that spur to form a pyramid.
00100 III. A. Euler Primitives. (Continued).
00200
00300 5. VNEW ← ESPLIT(E); Edge Split.
00400
00500 This primitive splits an edge by making a new vertex and a
00600 new edge. Its implementation is very similar to the midpoint example
00700 on page 19. ESPLIT is heavily used in the hidden line eliminator.
00800
00900 6. F ← KLFE(ENEW); Kill Face Edge.
01000
01100 This primitive Kills a face and an edge leaving one face.
01200 Since this primitive is intended to be an inverse of MKFE, the NFACE
01300 of ENEW is killed. However the NFACE and PFACE of an edge may be
01400 swapped by using the INVERT(E) primitive. See Figure 3.3 for KLFE.
01500
01600 7. E ← KLEV(VNEW); Kill Edge Vertex.
01700
01800 This primitive kills an edge and a vertex leaving one edge.
01900 This primitive will eliminate spurs made with MKEV and midpoints made
02000 with ESPLIT; in a pure form it would have to leave vertices with a
02100 valence greater than two untouched, however it in fact "un-pyramids"
02200 them with a series of KLFE's and then kills the remaining spur.
02300
02400 8. V ← KLVE(ENEW); Kill Vertex Edge.
02500
02600 This primitive kills a vertex and an edge leaving one vertex.
02700 This primitive is the face-vertex dual of KLFE, namely instead of
02800 killing NFACE of E and fixing up PFACE's perimeter, KLEV kills the
02900 NVT of E and fixes up PVT of E's perimeter.
03000
03100
03200 9. B ← GLUE(F1,F2); Glue two faces.
03300
03400 This primitive glues two faces together forming one new body
03500 out of two old ones (the body of F1 survives) or forming a handle on
03600 the given body. The number of edges in the two faces must be the same
03700 and their orientation should be opposite (exterior to exterior).
03800
03900 *10. BNEW ← UNGLUE(E); Unglue along seam. *not implemented.
04000
04100 This primitive unglues along the seam containing E. The
04200 UNGLUE primitive requires that a loop of edges be marked as a "seam"
04300 along which unglue will form two opposite faces. The marks are made
04400 in the temporary type bit in the edge nodes of the given body. If
04500 the cut forms two disjoint bodies then a new body is made on the
04600 NFACE side of the original E argument.
00100 III. B. SOLID PRIMITIVES.
00200
00300 1. VPEAK ← PYRAMID(F);
00400 2. F ← PRISM(F);
00500 3. F ← CWPRISMIOD(F);
00600 4. F ← CCWPRISMIOD(F);
00700
00800 These four primitives are called the "sweep primitives",
00900 because they form a simple polyhedron from a face in a fashion that
01000 appears like sweeping the face along. The sweep primitives (with the
01100 exception of PYRAMID) do not change the location of the given face
01200 but merely copy its perimeter, forming new faces and edges between
01300 the old perimeter and the new perimeter. The pyramid primitive has
01400 already appeared as an example on page 29.
01500
01600 Starting with a nine sided face lamina, the rocket in figure
01700 3.5 was formed from the bottom by sweeping two prism stages, then two
01800 counter clockwise prismoid stages, and then two clockwise prismoid
01900 stages, and finally one pyramid to form the nose cone. The fins were
02000 made by prism sweeping every third face of the first stage.
00100 III. B. SOLID PRIMITIVES. (continued).
00200
00300 5. ROTCOM(F); Rotation Completion.
00400
00500 As illustrated in the first three frames of figure 3.7 below,
00600 wire faces can be swept to form a shell. When a wire face is swept by
00700 a sweep primitive (other than pyramid) it is marked as a shell face
00800 of rotation and its original perimeter count is kept for later sweeps
00900 to refer to. In the third frame the shell has been positioned so
01000 that its slot can be seen. The shell face now includes all the edges
01100 of both pole caps as well as the two meridians of the slot. ROTCOM
01200 takes such a shell face and breaks it into two polar faces and as
01300 many other faces as necessary, by means of the count that was saved.
00100 FIGURE 3.8 - Face Vertex Duality.
00100 III. B. Solid Primitives. (continued).
00200
00300
00400 6. FVDUAL(B);
00500 7. BNEW←MKCOPY(B);
00600
00700 These two primitives illustrate the extremes from a class of
00800 miscellaneous primitives. FVDUAL is a worthless curosity and MKCOPY
00900 is quite useful but uninteresting. FVDUAL(B) of a body changes all
01000 the faces of a body into vertices and all the vertices into faces, in
01100 the winged edge data structure this merely requires computing a locus
01200 for each face (its center), re-"typing" faces and vertices, and then
01300 swapping the face and vertex link positions in each face, edge and
01400 vertex of the body.
01500
01600 Figure 3.8 illustrates Euclid's construction of a
01700 dodecahedron from a cube. The unit cube is formed, then all its edges
01800 are midpointed and translated 0.2 units into the three pairs of
01900 parallel faces; then the midpoints are lifted 0.3 units off the plane
02000 of each face of the cube; then MKFE is applied six times to split the
02100 eight sided faces into five sided faces; giving a dodecahedron
02200 (nearly regular). Applying the FVDUAL to the dodecahedron yields the
02300 icosahedron.
02400
02500
02600
00100 III. B. Solid Primitives. (continued).
00200
00300
00400 8. EVERT(B);
00500 9. B1←BUN(B1,B2);
00600 10. B1←BIN(B1,B2);
00700
00800 These three primitives perform the Boolean operations on
00900 polyhedron interior volumes. EVERT(B) turns a body inside out, thus
01000 changing a cube into a room, as a solid into a bubble. Objects with
01100 infinite "interiors" are permissible; such polyhedra are impossible
01200 in many classical developements of solid Geometry which make the
01300 interior of a polyhedron to be the region of space with finite
01400 volume, by definition. The body union is BUN, which allows B1 to
01500 survive if the interiors of the bodies are not disjoint. A body with
01600 two disjoint polyhedrons is shunned. The body intersection is BIN,
01700 which allows B1 to survive if the interiors of the bodies are not
01800 disjoint.
00100 C. GEOMETRIC PRIMITIVES.
00200
00300 1. TRANSLATE(Q,R); Q argument is a body, face, edge or vertex.
00400 2. ROTATE(Q,R); R argument is a transformation array with
00500 3. DILATE(Q,R); respect to world coordinates.
00600 4. REFLECT(Q,R);
00700
00800 The four Euclidean transformations are translation, rotation,
00900 reflection and dilation; and as first mentioned in Klein's Erlangen
01000 Program, 1872, these four primitives form a group. The primitives may
01100 be applied to bodies, faces, edges or vertices in order to change
01200 vertex world locii. Thus a body is the set of vertices in its vertex
01300 ring, a face is the set of vertices on its perimeter, an edge is the
01400 two vertices which are its ends, and a single vertex is itself; but
01500 there are special cases having to do with faces. (In GEOMED a
01600 special counter, negative Fcnt, is maintained in wire sweep faces in
01700 order to make solids of rotation). The second argument R is a pointer
01800 to a transformation array in world coordinates of four rows and three
01900 columns:
02000 XWC, YWC, ZWC
02100 IX, IY, IZ
02200 JX, JY, JZ
02300 KX, KY, KZ
02400
02500 For translation, only the XWC, YWC and ZWC are involved and all the
02600 vertices are translated in the obvious fashion:
02700
02800 X ← X + XWC; Y ← Y + YWC; Z ← Z + ZWC;
02900
03000 Whereas for rotation (dilation and reflection) the innermost
03100 computation applied to each vertex is:
03200
03300 X ← X + XWC; Y ← Y + YWC; Z ← Z + ZWC;
03400 XX ← IX*X + IY*Y + IZ*Z;
03500 YY ← JX*X + JY*Y + JZ*Z;
03600 ZZ ← KX*X + KY*Y + KZ*Z;
03700 X ← XX - XWC; Y ← YY - YWC; Z ← ZZ - ZWC;
03800
03900 At this point,I should now present a few general primitives for
04000 setting up such transformation arrays, but I don't have them yet. The
04100 problem involves selecting frames of references, strength of
04200 transformation, axes of transformations, origins of frames and modes
04300 such as absolute, relative or interpolated. At present in my
04400 applications these matters are handled ad hoc (the most general
04500 solution being the ROTDEL and EUCLID subroutines of GEOMED). The
04600 heart of deriving a transformation array is to get a frame of
04700 reference REF and an amount of rotation DEL and to compute the matrix
04800 product:
04900 R ← (transpose(REF)cross(DEL cross REF));
05000
05100 For dilation (larger or smaller) cross DEL with a non-unity diagonal
05200 matrix; for reflections flip the row signs on desired axes.
00100 D. IMAGE PRIMITIVES.
00200
00300 1. PROJECTOR(CAMERA,WORLD);
00400 2. ELIST←CLIPER(WINDOW,WORLD);
00500 3. OCCULT(WORLD);
00600 * 4. SHADOW(SUN,WORLD);
00700 * 5. TV ← MKVID(WINDOW,WORLD);
00800 * 6. B2D ← MKB2D(WINDOW,WORLD);
00900 * 7. B2D ← CAREYE(TV);
01000
01100 * under construction, Oct 1972.
01200
01300 PROJECTOR computes the perspective projected locus of all the
01400 vertices in a given world from a given camera. CLIPER computes the
01500 portions of 3D lines that are visible within a given display window.
01600 OCCULT compares all the edges, faces and vertices in a given world;
01700 using their current projected coordinates; faces, edges and vertices
01800 that are not visible from the implied camera's viewpoint are marked
01900 as hidden; faces, edges and vertices that are visible are marked as
02000 visible; and faces, edges and vertices that were initially partially
02100 visible are broken up into visible and hidden portions. The new
02200 faces, edges and vertices introduced by OCCULT are marked so that
02300 they can be removed.
02400
02500 The following four primitives are still being developed.
02600 SHADOW will literally build a world with shadows in it; shadow calls
02700 OCCULT twice, once for the SUN and once for the camera. There is no
02800 conceptual difficulty in doing many point sources, but I shall get
02900 one source working at a time. The MKVID primitive generates TV
03000 intensity rasters from the world model after OCCULT or SHADOW has
03100 been applied. The MKB2D primitive generates a 2D data structure of
03200 regions and edges (which is almost a copy of the 3D structure that
03300 has been presented, but with special attention paid to T-joints);
03400 this B2D data structure is an image model. Finally, the CAREYE
03500 primitive converts TV intensity rasters into B2D image structure. A
03600 detailed discription of these image primitives can not be given at
03700 this time (OCT 1972), because I haven't finished making them.
00100 IV. APPLICATIONS.
00200
00300 The single application around which the geometric modeling of
00400 this paper is being built is for a computer television vision (TVV ?)
00500 system for looking at real world scenes. I believe that a computer
00600 must have a means of representing what it is intended to see and
00700 further that the representation must have (in principle) an inverse
00800 relation to a television image. My first premise is rarely
00900 questioned, the second premise is frequentlty questioned. One
01000 alternative position is that so called "features" can be extracted
01100 from an image and then used by a heuristic problem solver to find an
01200 association between the perceived features and previous general
01300 knowledge; it is then stated that there is no need to go from the
01400 general knowledge or even from the so called image "features" back
01500 down to a television image, even just in principle. I wish to state
01600 the opposite, there is a need to go from the general representation
01700 to a television image in order to develop computer vision without
01800 having to solve several other problems of Artificial Intelligence.
01900 Applications of geometric modeling other than television vision might
02000 include: architectural drawing, computer animation, and modeling for
02100 laser, radar, and sonar image systems.
00100 IV. A. Modeling: GEOMED - a drawing program.
00200
00300 GEOMED, Geometric Model Editor, is for making and editing
00400 polyhedra. The command language of GEOMED provides the Euler
00500 primitives in the context of a push down stack (the PADPDL) of
00600 bodies, faces, edges and vertices. The main difference between an
00700 interactive program and a programming language being that the former
00800 carries along a working context so that most arguments and data do
00900 not have to be explicitly named.
01000
01100 V - make seminal vertex body.
01200 E - make edge and vertex.
01300 J - make edge and face.
01400 G - glue two faces.
01500
01600 In addition to the stack, GEOMED provides frames of reference
01700 for the Euclidean transformations; there is a world frame, body
01800 frames, camera frames, relative frame and face frames. Also the
01900 strength of a Euclidean transformation can be halved or double, set
02000 directly or entered numerically in several kinds of units. And
02100 finally the transformation can be done once or repeatedily by keying
02200 chords of Stanford's extra shift keys named "control" and "meta" with
02300 a ; : ( ) - or * character. These characters are not mnemonics but
02400 were chosen because of thier positions on the keyboard.
02500
02600 : ; - transform about X-axis.
02700 ( ) - transform about Y-axis.
02800 - * - transform about Z-axis.
02900
03000 no shifts - TRANSLATION.
03100 α - control - ROTATION.
03200 β - meta - DILATION.
03300 ε - meta-control - REFLECTION.
03400
03500 Finally, GEOMED provides access to all the solid primitives
03600 and hidden line elimination, along with commands for the stack,
03700 input, output, display, and switch toggling. The commands are
03800 detailed in the operating note, SAILON-68, along with a list of
03900 GEOMES and GEOMEL subroutines. Two examples should suffice to
04000 illustrate how concise and illegible GEOMED command strings are:
04100
04200 1. V:)\E;E(E:J↑/*S-↑ forms a cube.
04300 2. V:@E*E*E*E*E*E*E*J↑!
04400 \\:@S)S)S)S)S)S)S)S)G↑ forms a torus.
04500
04600 Thus a polyhedron can be represented in a few characters (which must
04700 be compiled); one might hope that such a "representation by
04800 generation" could provide a link between semantic and geometric
04900 models. The hard direction is to get from a polyhedron model to the
05000 command string.
00100 IV. B. Graphics: OCCULT - a hidden line eliminator.
00200
00300 OCCULT is a hidden line eliminator; it is neither a Watkins
00400 nor a Warnock algorithm but is rather a throw-back to the naive idea
00500 of comparing each edge with all the other edges and having ways to
00600 dampen the potentially large number of comparisons that might occur.
00700
00800 There are three kinds of dampening in OCCULT. The first (used
00900 in other hidden eliminators) is to get rid of the faces that have
01000 their backs to the camera and to consider for comparision only the
01100 edges with one potentially visible face. These edges are called
01200 "folds". The second kind of dampening, is to hide everything
01300 connected to the hidden portion of an edge when a fold crossing is
01400 discovered, this is made possible by the winged edge primitives which
01500 allow polyhedron surfaces to be easily traversed topologically; and
01600 by the Euler primitives which allows the edges to be quickly broken
01700 into visible and hidden portions without losing their topology. The
01800 third kind of dampening involves having a raster of edge buckets to
01900 localize the comparisons.
02000
02100 The reason for doing hidden line elimination in this fashion
02200 is to get the topology of the image regions and edges in a modeled
02300 scene including the shadows. OCCULT was used to make some of the
02400 figures that appeared earlier in this paper; for example the arm
02500 model in figure 1.2, (which required twelve seconds of PDP-10 compute
02600 time). A paper on OCCULT should be available before the end of the
02700 year, 1972.
02800
02900
03000 IV. C. Vision: CAREYE - a video region-edge finder.
03100
03200 CAREYE, Cart Eye, is the oldest, most rewritten, yet least
03300 finished part of the application. At present its best trick is to
03400 take a Television image and convert it into video intensity contour
03500 lines similar to those discussed by Krakaur and Horn (of M.I.T.).
03600 From VIC, Video Intensity Contours, the image goes through two
03700 processes: first, the camera locus-orientation for the image is
03800 solved by finding feature points in the image that coorespond with
03900 known land mark point in the world; and second, after the camera is
04000 solved,the locus of previously unknown regions of the image must be
04100 added to the world model; the third dimension of such unknown regions
04200 being assumed to be very large, until evidence is found in succeeding
04300 images that make the region "pop out" of the background. These two
04400 processes are called Camera Locus Solving and Body Locus Solving;
04500 CAMLS and BODLS; and are the missing links in making polyhedron
04600 models merely by looking at objects and scenes of objects.
00100 References:
00200
00300 1. AGIN
00400 Representation and Description of Curved Objects
00500 Stanford Artificial Intelligence AIM-172, 1972.
00600
00700 2. COXETER
00800 Introduction to Geometry
00900 John Wiley & Sons, Inc. New York. 1961.
01000
01100 3. EVES
01200 A Survey of Geometry.
01300 Allyn and Bacon, Inc. Boston. 1965.
01400
01500 4. FALK
01600 Computer Interpretation of Imperfect Line Data
01700 as a Three Dimensional Scene.
01800 Stanford Artificial Intelligence AIM-132, 1970.
01900
02000 5. FELDMAN, FALK & PAUL
02100 Computer Representation of Simply Described Scenes.
02200 Stanford Artificial Intelligence SAILON-52, 1969.
02300
02400 6. GUZMAN
02500 Computer Recognition of Three Dimensional Objects.
02600 Project MAC Technical Report, 1968.
02700
02800 7. KNUTH
02900 The Art of Computer Programming.
03000 Volume 1 - Fundamental Algorithms.
03100 Chapter 2 - Information Structures.
03200 Addison-Wesley. Reading,Mass. 1968.
03300
03400 8. ROBERTS
03500 Machine Perception of Three Dimensional Solids
03600 Lincoln Laboratory Technical Report #315, 1963.
03700
03800 9. SOBEL
03900 Camera Models and Machine Perception.
04000 Stanford Artificial Intelligence AIM-121, 1970.